package org.datacoder.geocoding.datastructures.rectangles

import org.datacoder.geocoding.*
import org.datacoder.geocoding.datastructures.geoshapes.*
import org.datacoder.geocoding.datastructures.util.*
import org.datacoder.geocoding.jurisdiction.Jurisdiction

class KDIntervalTree implements RectanglesContainingPointFinder {

    public KDIntervalTreeNode root

    public KDIntervalTree(Collection<Jurisdiction> jurisdictions){
        List<GeoRectangle> geoRectangles = new ArrayList<GeoRectangle>()
        for(juris in jurisdictions){
            geoRectangles.add(juris.toGeoRectangle())
        }
        root = createNode(geoRectangles)
    }

    public KDIntervalTreeNode createNode(List<GeoRectangle> geoRectangles){
        if(geoRectangles.isEmpty()){
            return null
        }

        KDIntervalTreeNode kditNode
        double minLon = 1000
        double maxLon = -1000
        double minLat = 1000
        double maxLat = -1000
        double lonDifference
        double latDifference

        for(gr in geoRectangles){
            if(gr.lon1 < minLon){
                minLon = gr.lon1
            }else if(maxLon < gr.lon1){
                maxLon = gr.lon1
            }
            if(gr.lat1 < minLat){
                minLat = gr.lat1
            }else if(maxLat < gr.lat1){
                maxLat = gr.lat1
            }
        }

        lonDifference = maxLon - minLon
        latDifference = maxLat - minLat

        int type
        if(lonDifference >= latDifference){
            type = GeoShape.LON
        }else{
            type = GeoShape.LAT
        }

        kditNode = new KDIntervalTreeNode(type)

        Collections.sort(geoRectangles, new GeoRectangleStartPointComparator(type))
        int numGeoRectangles = geoRectangles.size()
        kditNode.center = geoRectangles.get((Integer)(numGeoRectangles/2)).retrieveCenter(type)

        List<GeoRectangle> leftGeoRectangles = new ArrayList<GeoRectangle>()
        List<GeoRectangle> rightGeoRectangles = new ArrayList<GeoRectangle>()

        int i
        for(i = 0; i < numGeoRectangles; i++){
            GeoRectangle gr = geoRectangles.get(i)
            if(gr.retrieveMinValue(type) > kditNode.center){
                break
            }
            if(gr.retrieveMaxValue(type) > kditNode.center){
                kditNode.addGeoRectangle(gr)
            }else{
                leftGeoRectangles.add(gr)
            }
        }
        for(; i < numGeoRectangles; i++){
            rightGeoRectangles.add(geoRectangles.get(i))
        }
        kditNode.left = createNode(leftGeoRectangles)
        kditNode.right = createNode(rightGeoRectangles)
        return kditNode
    }

    public Set<Jurisdiction> findRectanglesContainingPoint(GeoPoint gp){
        Set<Jurisdiction> jurisdictions = new HashSet<Jurisdiction>()
        KDIntervalTreeNode kditNode = root
        while(kditNode != null){
            if(gp.retrieveValue(kditNode.type) == kditNode.center){
                jurisdictions.addAll(GeocodingUtils.convertGeoShapesToJurisdictions(kditNode.geoRectanglesByStart))
                break
            }else if(gp.retrieveValue(kditNode.type) < kditNode.center){
                for(gr in kditNode.geoRectanglesByStart){
                    if(gr.retrieveMinValue(kditNode.type) > gp.retrieveValue(kditNode.type)){
                        break
                    }
                    if(gr.containsGeoPoint(gp)){
                        jurisdictions.add(gr.juris)
                    }
                }
                kditNode = kditNode.left
            }else{
                for(gr in kditNode.geoRectanglesByEnd){
                    if(gr.retrieveMaxValue(kditNode.type) < gp.retrieveValue(kditNode.type)){
                        break
                    }
                    if(gr.containsGeoPoint(gp)){
                        jurisdictions.add(gr.juris)
                    }
                }
                kditNode = kditNode.right
            }
        }
        return jurisdictions
    }
}

